package leetcode;


public class Solution106 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0) return null;
        return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    public TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd){
        System.out.println("inStart----->" + inStart + ", inEnd------>" + inEnd + ", postStart------>" + postStart + ", postEnd----->" + postEnd);
        if(inStart > inEnd || postEnd < 0 || postStart > postEnd || postStart < 0 ) {
            System.out.println(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>");
            return null;
        }
        TreeNode node = new TreeNode(0);
        int val = postorder[postEnd];
        System.out.println("val ==============================================" + val);
        node.val = val;
        int index = -1;
        for(int i = 0; i <= inEnd; i++){
            if(val == inorder[i]){
                index = i;
                break;
            }
        }
        node.left = buildTree(inorder, inStart, index - 1 , postorder, postStart, index - 1 );
        node.right = buildTree(inorder, index + 1, inEnd, postorder, index, postEnd - 1);
        return node;
    }

    public static void main(String[] args) {
       /* int[] inorder = {9,3,15,20,7};
        int[] postorder = {9,15,7,20,3};*/
        int[] inorder = {9,8,6,3,15,20,7};
        int[] postorder = {9,6,8,15,7,20,3};
        System.out.println(new Solution106().buildTree(inorder, postorder));
    }
}
